class Solution:

    # The feeling is just different!!!
    # diag1和diag2参数的作用是
    def dfs(self,row,cols,diag1,diag2,n):
        if row == n:    # 从上往下进行，直到row到达n为止，原理还是基础递归版本一样
            return 1
                        # 因为最后一行肯定可以放下一个，而且这种方法不占用公共区域，所以直接返回1。
        # 临时计数变量
        count = 0

        # 这样来获得纵向上看可以下皇后的位置？？？
        # 首先把cols和diag1和diag2或在一起
        # 然后再按位取反，然后再位与上一大堆1
        available_positions = ~(cols | diag1 | diag2) & ((1 << n) - 1)  
        # 这里利用n位掩码，来让这些二进制数字不要位溢出
        
        # 只要可利用位置(使用0和1表示的序列)不全为0，
        # 就可开始对count进行加加

        while available_positions:      # 这个是循环变量，每次循环都在往
            # 一个数字按位与上负的这个数字？？？
            # 等于他最低位的1！！！！
            # 那么这不就意味着从后往前放吗？？？
            position = available_positions & -available_positions

            # 对count进行变化从下往上，最底下一行先反馈过来，只有一个1
            # 一层一层把临时结果反馈回来，最终返回最终结果
        
            count += self.dfs(
                row + 1, 
                cols | position, 
                (diag1 | position) << 1,    
                (diag2 | position) >> 1,
                n)
            
            # row+1是往下一行进行
            # cols|position是把占用情况合并一下，如果占用体现在cols中为1
            # diag1和diag2是一种抽象化操作
            # 使用二进制的每一位来表示每一条主对角线和副对角线是否被占用
            
            # 这里是消除最低位的1
            available_positions &= available_positions - 1
        
        return count
    # 



    # 
    def solve(self,n):
        return self.dfs(0,0,0,0,n)

if __name__ == "__main__":
    s = Solution()
    print(s.solve(8))